package com.example.algo.twosum;

import java.util.*;

/**
 * 两数之和
 * <p>
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 * <p>
 * 示例:
 * <p>
 * 给定 nums = [2, 7, 11, 15], target = 9
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 */
public class Solution {


    public static void main(String[] args) {
        testTwoSum();

//        int[] nums = {2, 7, 11, 15};
//        int target = 9;
//        twoSum(nums, target);
    }


    /**
     * 测试 两数之和
     * 随机生成一个大数组
     */
    public static void testTwoSum() {
        Calendar calendar = Calendar.getInstance();
        calendar.clear();
        calendar.setTime(new Date());

        Long startDate = calendar.getTimeInMillis();
        System.out.printf("begin->:\t%s\n", startDate);


        int size = 1000000000;
        int arrLen = 176160813;

        Random random = new Random();
        // 随机生成数组长度
//        arrLen = random.nextInt(size);
        System.out.printf("arrLen:%s\n", arrLen);

        // 生成数组数据
        int[] nums = new int[arrLen];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = random.nextInt(size);
        }
        // 计算目标数
        int target = nums[random.nextInt(arrLen)] + nums[random.nextInt(arrLen)];

        calendar.clear();
        calendar.setTime(new Date());
        Long middle = calendar.getTimeInMillis();
        System.out.printf("middle->:\t\t%s\n", middle);
        System.out.printf("生成数组耗时:%s\n", (middle - startDate));

        System.out.printf("target->:%s\n", target);
        int[] re = twoSum(nums, target);
        for (int n : re) {
            System.out.printf("index:%s -> num:%s\n", n, nums[n]);
        }

        calendar.clear();
        calendar.setTime(new Date());
        Long endDate = calendar.getTimeInMillis();
        System.out.printf("end->:\t\t%s\n", endDate);
        System.out.printf("总耗时:%s\n", (endDate - startDate));
    }

    /**
     * 时间复杂度 O(n) 我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 时间
     * 空间复杂度 O(n)  所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {

        // 计算时间
        Calendar calendar = Calendar.getInstance();
        calendar.clear();
        calendar.setTime(new Date());
        Long startDate = calendar.getTimeInMillis();
        System.out.printf("startDate->:\t%s\n", startDate);

        // 正式开始
        int[] re = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int result = target - nums[i];
            if (map.containsKey(result)) {
                re[0] = map.get(result);
                re[1] = i;
                break;
            }
            map.put(nums[i], i);
        }
        // 正式结束

        // 计算时间
        calendar.clear();
        calendar.setTime(new Date());
        Long endDate = calendar.getTimeInMillis();
        System.out.printf("endDate->:\t\t%s\n", endDate);
        System.out.printf("查找耗时:%s\n", endDate - startDate);
        return re;
    }
}
